package leetcode;

/**
 * 二叉搜索树的范围和
 */
class T938 {

    public static void main(String[] args) {
        int[] root = new int[]{10, 5, 15, 3, 7, -1, 18};
        TreeNode rootNode = new TreeNode(root[0]);
        int low = 7;
        int high = 15;
        //构建二叉搜索树
        for (int i = 1; i < root.length; i++) {
            TreeNode tmpNode ,preNode;
            tmpNode= preNode= rootNode;
            while(tmpNode!=null){
                preNode = tmpNode;
                if(tmpNode.val>root[i]){
                    tmpNode = tmpNode.left;
                }else{
                    tmpNode = tmpNode.right;
                }
            }
            if(preNode.val>root[i]){
                preNode.left = new TreeNode(root[i]);
            }else{
                preNode.right = new TreeNode(root[i]);
            }
        }

        T938 t = new T938();
        System.out.println( t.rangeSumBST(rootNode, low, high));
    }

    //深搜
    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        if (root == null) {
            return sum;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        if ( root.val >= low && root.val<= high) {
            sum += root.val + rangeSumBST(left, low, high) + rangeSumBST(right, low, high);
        }
        else if(root.val<low){
            sum += rangeSumBST(right, low, high);
        }else if(root.val> high) {
            sum += rangeSumBST(left, low, high);
        }

        return sum;
    }


}